#include <bits/stdc++.h>

using namespace std;

const int maxn=105;

typedef long long ll;
const ll inf=~0ULL>>3;
ll f[70][maxn][maxn];
ll _p[2][maxn][maxn];
ll (*p)[maxn],(*q)[maxn];

template <typename T> inline void read(T &r){
    char c;bool _f=0;
    for(c=getchar();c>'9'||c<'0';c=getchar()) if(c=='-') _f=1;
    for(r=0;c<='9'&&c>='0';c=getchar()) r=r*10+c-'0';
    if(_f) r=-r;
}
template <typename T> void write(T n){
    if(n<0) putchar('-'),n=-n;
    if(n>9) write(n/10);
    putchar(n%10+'0');
}

int main(){
    int T;
    read(T);
    while(T--){
        ll n,m;
        read(n);read(m);
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++){
                ll w;
                read(w);
                if(w) f[0][i][j]=w;
                else f[0][i][j]=-inf;
            }
        bool flag=1;
        int lg=0;
        for(;flag;lg++){
            for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) f[lg+1][i][j]=-inf;
            for(int k=1;k<=n;k++)
                for(int i=1;i<=n;i++)
                    for(int j=1;j<=n;j++){
                        f[lg+1][i][j]=max(f[lg+1][i][j],f[lg][i][k]+f[lg][k][j]);
                        if(i==1&&f[lg+1][i][j]>=m) flag=0;
                    }
        }
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++)
                _p[0][i][j]=_p[1][i][j]=-inf;
        p=_p[0];q=_p[1];
        for(int i=1;i<=n;i++) p[i][i]=0;
        ll ans=0;
        for(;lg>=0;lg--){
            bool fl=1;
            for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) q[i][j]=-inf;
            for(int k=1;k<=n;k++)
                for(int i=1;i<=n;i++)
                    for(int j=1;j<=n;j++){
                        q[i][j]=max(q[i][j],p[i][k]+f[lg][k][j]);
                        if(i==1&&q[i][j]>=m) fl=0;
                    }
            if(fl){
                swap(p,q);
                ans|=1ll<<lg;
            }
        }

        write(ans+1);putchar('\n');
    }
    return 0;
}
